// Copyright (c) 2012-2013, IGN France.
// Copyright (c) 2012-2024, Oslandia.
// Copyright (c) 2024-2025, SFCGAL team.
// SPDX-License-Identifier: LGPL-2.0-or-later

// Copyright (c) 2012-2024, SFCGAL Contributors and Oslandia
// SPDX-License-Identifier: LGPL-2.0-or-later

#include <boost/test/unit_test.hpp>

#include "SFCGAL/GeometryCollection.h"
#include "SFCGAL/Solid.h"
#include "SFCGAL/algorithm/area.h"
#include "SFCGAL/algorithm/covers.h"
#include "SFCGAL/algorithm/minkowskiSum3D.h"
#include "SFCGAL/algorithm/volume.h"
#include "SFCGAL/detail/tools/Registry.h"
#include "SFCGAL/io/wkt.h"
#include "SFCGAL/primitive3d/Sphere.h"

using namespace SFCGAL;
using namespace boost::unit_test;

BOOST_AUTO_TEST_SUITE(SFCGAL_algorithm_MinkowskiSum3DTest)

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_Sphere_Polyline)
{
  // Create a sphere
  Kernel::FT      radius(10.0);
  int             num_vertical   = 4;
  int             num_horizontal = 8;
  Kernel::Point_3 center(0, 0, 0);
  Sphere          sphere(radius, center, num_vertical, num_horizontal);
  std::unique_ptr<Geometry> sphereGeom(
      new PolyhedralSurface(sphere.generatePolyhedron()));

  // Create a polyline
  std::vector<Point> polyline_points = {Point(-100, 0, 0), Point(40, -70, 0),
                                        Point(40, 50, 40), Point(-90, -60, 60),
                                        Point(0, 0, -100), Point(30, 0, 150)};
  LineString         polyline(polyline_points);

  // Perform Minkowski sum
  std::unique_ptr<Geometry> result =
      algorithm::minkowskiSum3D(*sphereGeom, polyline);

  // Check that the result is not empty
  BOOST_CHECK(!result->isEmpty());

  // Check that the result is a PolyhedralSurface
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_POLYHEDRALSURFACE);

  std::string expectedWkt =
      "POLYHEDRALSURFACE "
      "Z(((71467610562386210374276105590405/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-"
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "71467610562386210374276105590405/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),(("
      "14514190286063188049905/725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-"
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-7258176006942162944015/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),(("
      "142935221124772406906054517161905/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-"
      "44087981245209065237720472518735/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,"
      "142935221124772406906054517161905/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),((-"
      "44087981245209065237720472518735/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-7258176006942162944015/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "44087981245209065237720472518735/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248)),((-"
      "1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-44087981245209065237720472518735/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-"
      "1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344)),((-344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-44087981245209065237720472518735/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-7258176006942162944015/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344)),((-"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-22043990622604525697611389249915/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344)),((-22043990622604525697611389249915/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-7258176006942162944015/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248)),(("
      "175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,71467610562386210374276105590405/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "71467610562386210374276105590405/3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,"
      "175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((71467610562386210374276105590405/"
      "3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,71467610562386210374276105590405/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "71467610562386210374276105590405/3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),(("
      "350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,71467610562386210374276105590405/"
      "3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "71467610562386210374276105590405/3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,14514190286063188049905/"
      "725745543100178366464 "
      "18629091000080665/10141204801825835211973625643008 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "142935221124772406906054517161905/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),((-"
      "198070406285660833744625694417/39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/"
      "1125899906842624,-548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-7961314590657215/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624)),((-7961314590657215/"
      "1125899906842624 8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-22043990622604525697611389249915/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-7961314590657215/"
      "1125899906842624 8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,-7961314590657215/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,71467610562386210374276105590405/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,25815682614621505/"
      "1125899906842624 8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((71467610562386210374276105590405/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-7961314590657215/"
      "1125899906842624 8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-22043990622604525697611389249915/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,"
      "71467610562386210374276105590405/3117053372833024535729583161344 "
      "15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),(("
      "63382530011411472322409066011315/2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/17592186044416,25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,"
      "175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/"
      "17592186044416)),((175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,71467610562386210374276105590405/"
      "3117053372833024535729583161344 15922629181314435/2251799813685248 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,"
      "175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((-15922629181314435/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-15922629181314435/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((-44087981245209065237720472518735/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-15922629181314435/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,-"
      "44087981245209065237720472518735/6234106745666049071459166322688 "
      "-31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248)),((-"
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,-15922629181314435/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-"
      "1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/"
      "1125899906842624)),((-1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-15922629181314435/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-44087981245209065237720472518735/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "-2807588736565171610977864486166182023976077484691/"
      "28075920816769514077629486313367973723266613248,-"
      "1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344)),((51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/"
      "17592186044416,350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248,51631365229243005/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,"
      "350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,142935221124772406906054517161905/"
      "6234106745666049071459166322688 -31845258362628855/4503599627370496 "
      "4211391467627206908429507092175811406840575827309/"
      "28075920816769514077629486313367973723266613248)),((-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464,-1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464)),((-"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464,-344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "463475168717572581600348013527/"
      "356811923176489970264571492362373784095686656 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344)),((0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1,-396140812571321791884791867853/79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/725745543100178366464,0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1)),((-720575940379279375/725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464,-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/"
      "1125899906842624,-1096933437619888831972918068152448635309232193/"
      "219343131381011828731480361823187294713020416 "
      "-792281625142643210582962298649/158456325028528675187087900672 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/725745543100178366464)),((0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1,-720575940379279375/725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464,-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624,0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1)),((-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624,-720575940379279375/"
      "725745543100178366464 0/1 "
      "-79831923271906774797515/"
      "725745543100178366464,-548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "396140812571321791884791867853/79228162514264337593543950336 "
      "-333745861673796980205727832385915/"
      "3117053372833024535729583161344,-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624)),((21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464,175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,71467610562386210374276105590405/"
      "3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464)),(("
      "350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464,71467610562386210374276105590405/"
      "3117053372833024535729583161344 "
      "29662410797924641496604072849595/"
      "22835963083295358096932575511191922182123945984 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,"
      "350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/725745543100178366464,30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1,63382530011411472322409066011315/2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/17592186044416,21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464)),(("
      "175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464,63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/"
      "17592186044416,175467536121934928387714809923801403646175422015/"
      "7018980204192378519407371578341993430816653312 "
      "25353012004564591496100843279705/5070602400912917605986812821504 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1,21771645717064971714545/725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464,126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/"
      "17592186044416)),((350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896,126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,21771645717064971714545/"
      "725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464,350935072243869834734533847341290560432633914115/"
      "14037960408384757038814743156683986861633306624 "
      "-50706024009129159108257914587765/10141204801825835211973625643008 "
      "7649988641866746577951358290839/"
      "48703958950516008370774736896)),((617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624)),((24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624,-7961314590657215/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-7961314590657215/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1,-198070406285660833744625694417/39614081257132168796771975168 "
      "396220040733836056224034679245/79228162514264337593543950336 "
      "-120551305274919615/1125899906842624,617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/"
      "1125899906842624)),((1370157784997721525365835594571039980171064110905/"
      "45671926166590716193865151022383844364247891968 "
      "8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/"
      "17592186044416,1370157784997721525365835594571039980171064110905/"
      "45671926166590716193865151022383844364247891968 "
      "8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416)),((63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/17592186044416,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,25815682614621505/1125899906842624 "
      "8153539062337597567/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/17592186044416)),((30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1,1370157784997721525365835594571039980171064110905/"
      "45671926166590716193865151022383844364247891968 "
      "8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,63382530011411472322409066011315/"
      "2535301200456458802993406410752 "
      "25358082606965504413812383208793/5070602400912917605986812821504 "
      "2763223447141419/17592186044416,30/1 "
      "1152921504606847/1152921504606846976 160/1)),((0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,30/"
      "1 -11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((-15922629181314435/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,0/"
      "1 -11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,-15922629181314435/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,0/1 "
      "-8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624)),((-15922629181314435/"
      "2251799813685248 -8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,-15922629181314435/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((30/1 "
      "-11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,30/"
      "1 -8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,30/1 "
      "-11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,30/"
      "1 -11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,126765060022822936683503541365415/"
      "5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,51631365229243005/2251799813685248 "
      "-8153539062337593727/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((0/1 "
      "-1152921504606847/1152921504606846976 -110/1,0/1 "
      "-8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,-396140812571321791884791867853/"
      "79228162514264337593543950336 "
      "-792440081467671739261447921433/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,0/1 "
      "-1152921504606847/1152921504606846976 -110/1)),((30/1 "
      "-8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1,126765060022822936683503541365415/5070602400912917605986812821504 "
      "-50716165213930984943680994445941/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,30/1 "
      "-8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416)),((720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/725745543100178366464,0/1 "
      "-1152921504606847/1152921504606846976 -110/1,0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1,720575940379279375/725745543100178366464 0/1 "
      "-79832096210132465824565/725745543100178366464)),((0/1 "
      "1152921504606847/1152921504606846976 -110/1,0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1,-720575940379279375/725745543100178366464 0/1 "
      "-79831923271906774797515/725745543100178366464,0/1 "
      "1152921504606847/1152921504606846976 -110/1)),((0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1,198070406285660833744625694417/39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,0/1 "
      "-8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1)),((548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464,548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),((720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464,198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,0/1 "
      "-1152921504606847/1152921504606846976 "
      "-110/1,720575940379279375/725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464)),(("
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464,792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/"
      "1125899906842624,2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),((792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624,720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/725745543100178366464,0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1,792281625142643459374043256687/158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624)),((617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624,0/1 "
      "1152921504606847/1152921504606846976 "
      "-110/1,617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624)),((30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1,21773086868945730273295/725745543100178366464 0/1 "
      "116119200426915693120715/725745543100178366464,30/1 "
      "1152921504606847/1152921504606846976 160/1,30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1)),((21771645717064971714545/725745543100178366464 0/1 "
      "116119373365141384147765/725745543100178366464,30/1 "
      "-1152921504606847/1152921504606846976 160/1,30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1,21771645717064971714545/725745543100178366464 0/1 "
      "116119373365141384147765/"
      "725745543100178366464)),((354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/"
      "17592186044416,1370157784997721525365835594571039980171064110905/"
      "45671926166590716193865151022383844364247891968 "
      "8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416)),((21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/"
      "725745543100178366464,982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416,21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/725745543100178366464)),((30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1,21773086868945730273295/725745543100178366464 0/1 "
      "116119200426915693120715/"
      "725745543100178366464,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416,30/1 "
      "1152921504606847/1152921504606846976 "
      "160/1)),((88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/"
      "17592186044416,245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/"
      "725745543100178366464,88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416)),((30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1,88735542015976055857195318633805/2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/725745543100178366464,30/1 "
      "-1152921504606847/1152921504606846976 "
      "160/1)),((88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,30/1 "
      "-1152921504606847/1152921504606846976 160/1,30/1 "
      "-8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416)),((166953247183743745/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,166953247183743745/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624,617966891623430150265644177709/"
      "713623846352979940529142984724747568191373312 "
      "8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,24838788000107555/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((166953247183743745/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416,166953247183743745/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416,608472288109550137557205538688035/"
      "20282409603651670423947251286016 "
      "11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,"
      "1370157784997721525365835594571039980171064110905/"
      "45671926166590716193865151022383844364247891968 "
      "8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416)),((7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,30/"
      "1 -11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,30/"
      "1 -11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((0/1 "
      "-8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,0/"
      "1 -8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624)),((0/1 "
      "-11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,0/"
      "1 -8153539062337596031/1152921504606846976 "
      "-120551305274919615/1125899906842624,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/10141204801825835211973625643008,0/"
      "1 -11530367967573076607/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,30/1 "
      "-8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((30/1 "
      "-11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/10141204801825835211973625643008,30/"
      "1 -8153539062337595007/1152921504606846976 "
      "2763223447141419/17592186044416,30/1 "
      "-11530367967573076607/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464,344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),(("
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,720575940379279375/"
      "725745543100178366464 0/1 "
      "-79832096210132465824565/"
      "725745543100178366464,2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),(("
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,22043990622604525697611389249915/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,7961314590657215/"
      "1125899906842624 -8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),((198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/"
      "1125899906842624,548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,198070406285660833744625694417/"
      "39614081257132168796771975168 "
      "-792440081467671988052528879471/158456325028528675187087900672 "
      "-120551305274919615/1125899906842624)),((344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),(("
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,344437353478195757282983250839/"
      "48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,22043990622604525697611389249915/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "548466718809944243791960811370638260160430677/"
      "109671565690505914365740180911593647356510208 "
      "-792281625142643459374043256687/158456325028528675187087900672 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),((88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)),((31845258362628865/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,"
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,792281625142643459374043256687/"
      "158456325028528675187087900672 "
      "198110020366917965914247100113/39614081257132168796771975168 "
      "-120551305274919615/1125899906842624,31845258362628865/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)),(("
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "344437353478195757282983250839/48703958950516008370774736896 "
      "-617966891623430150265644177709/"
      "1427247692705959881058285969449495136382746624 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344,"
      "2193866875239777319556839690893725155630093547/"
      "438686262762023657462960723646374589426040832 "
      "198070406285660833744625694417/39614081257132168796771975168 "
      "-333746604437820551433908233742715/"
      "3117053372833024535729583161344)),((115555591807595261769498884090235/"
      "3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,"
      "982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/"
      "725745543100178366464,115555591807595261769498884090235/"
      "3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),(("
      "245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,115555591807595261769498884090235/"
      "3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,21773086868945730273295/"
      "725745543100178366464 0/1 "
      "116119200426915693120715/"
      "725745543100178366464,245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),(("
      "982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,462222367230381060920493230379845/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,166953247183743745/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,"
      "982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),((354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/"
      "17592186044416,982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,166953247183743745/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,354942168063904231390095865192435/"
      "10141204801825835211973625643008 "
      "12679041303482748226248896275789/2535301200456458802993406410752 "
      "2763223447141419/17592186044416)),((115555591807595261769498884090235/"
      "3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,29030542299947513937935/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "462222367230381060920493230379845/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),(("
      "982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,115555591807595261769498884090235/"
      "3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,462222367230381060920493230379845/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "982685104518431153147805711613185055671012036735/"
      "28075920816769514077629486313367973723266613248 "
      "12676506002282291767393126311245/2535301200456458802993406410752 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),((41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,115555591807595261769498884090235/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416,41738311795935935/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,"
      "245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,88735542015976055857195318633805/"
      "2535301200456458802993406410752 "
      "-50716165213931000866310175760371/10141204801825835211973625643008 "
      "2763223447141419/17592186044416)),((115555591807595261769498884090235/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,29030542299947513937935/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,115555591807595261769498884090235/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248)),(("
      "245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,115555591807595261769498884090235/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-39549881063899524649243627351865/"
      "91343852333181432387730302044767688728495783936 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896,"
      "245671276129607782776727484776718202202823776705/"
      "7018980204192378519407371578341993430816653312 "
      "-50706024009129175030887095902195/10141204801825835211973625643008 "
      "7649977036178878277511039519639/"
      "48703958950516008370774736896)),((462222367230381060920493230379845/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "88175962490418116632943251018565/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,166953247183743745/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,462222367230381060920493230379845/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248)),((166953247183743745/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,88175962490418116632943251018565/"
      "12468213491332098142918332645376 7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,31845258362628865/"
      "4503599627370496 8153539062337595007/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,166953247183743745/4503599627370496 "
      "8153539062337595007/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008)),((22043990622604525697611389249915/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,41738311795935935/"
      "1125899906842624 -8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,22043990622604525697611389249915/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)),((7961314590657215/"
      "1125899906842624 -8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008,22043990622604525697611389249915/"
      "3117053372833024535729583161344 -31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,41738311795935935/"
      "1125899906842624 -8153539062337596287/1152921504606846976 "
      "1521180720273875288005740846478089/"
      "10141204801825835211973625643008,7961314590657215/1125899906842624 "
      "-8153539062337596287/1152921504606846976 "
      "-1014120480182583514987665564273911/"
      "10141204801825835211973625643008)),((7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,29030542299947513937935/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)),(("
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "115555591807595261769498884090235/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,"
      "22043990622604525697611389249915/3117053372833024535729583161344 "
      "-31845258362628865/4503599627370496 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)),(("
      "462222367230381060920493230379845/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,29030542299947513937935/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "462222367230381060920493230379845/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248)),(("
      "88175962490418116632943251018565/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "462222367230381060920493230379845/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "4211384777403647349242425363205910007051197881709/"
      "28075920816769514077629486313367973723266613248,7258176006942162944015/"
      "725745543100178366464 "
      "-24838788000107555/40564819207303340847894502572032 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248,"
      "88175962490418116632943251018565/12468213491332098142918332645376 "
      "7961314590657215/1125899906842624 "
      "-2807595426788731170164946215136083423765455430291/"
      "28075920816769514077629486313367973723266613248)))";

  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  // flaky
  // BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  // flaky on mingw
  // BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_Cube_Point)
{
  // Create a cube
  std::string cubeWkt =
      "SOLID ((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)), ((0 0 0, 0 0 1, 0 1 1, 0 "
      "1 0, 0 0 0)), ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)), ((1 1 1, 0 1 1, 0 "
      "0 1, 1 0 1, 1 1 1)), ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)), ((1 1 1, 1 "
      "1 0, 0 1 0, 0 1 1, 1 1 1))))";
  std::unique_ptr<Geometry> cube(io::readWkt(cubeWkt));

  // Create a point
  Point point(5, 5, 5);

  // Perform Minkowski sum
  std::unique_ptr<Geometry> result = algorithm::minkowskiSum3D(*cube, point);

  // Check that the result is not empty
  BOOST_CHECK(!result->isEmpty());

  // Check that the result is a PolyhedralSurface
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_POLYHEDRALSURFACE);

  // BOOST_CHECK_EQUAL(result->asText(1), "POLYHEDRALSURFACE
  // Z
  // (((5.0 6.0 6.0,5.0 6.0 5.0,5.0 5.0 6.0,5.0 6.0 6.0)),((5.0 5.0 6.0,5.0 6.0 5.0,5.0
  // 5.0 5.0,5.0 5.0 6.0)),((6.0 5.0 5.0,6.0 5.0 6.0,5.0 5.0 6.0,6.0 5.0 5.0)),((5.0
  // 5.0 5.0,6.0 5.0 5.0,5.0 5.0 6.0,5.0 5.0 5.0)),((5.0 5.0 5.0,5.0 6.0 5.0,6.0 5.0
  // 5.0,5.0 5.0 5.0)),((6.0 5.0 5.0,5.0 6.0 5.0,6.0 6.0 5.0,6.0 5.0 5.0)),((6.0 5.0
  // 6.0,6.0 6.0 6.0,5.0 6.0 6.0,6.0 5.0 6.0)),((5.0 5.0 6.0,6.0 5.0 6.0,5.0 6.0 6.0,5.0
  // 5.0 6.0)),((5.0 6.0 5.0,5.0 6.0 6.0,6.0 6.0 5.0,5.0 6.0 5.0)),((6.0 6.0 5.0,5.0
  // 6.0 6.0,6.0 6.0 6.0,6.0 6.0 5.0)),((6.0 5.0 6.0,6.0 5.0 5.0,6.0 6.0 5.0,6.0 5.0
  // 6.0)),((6.0 6.0 6.0,6.0 5.0 6.0,6.0 6.0 5.0,6.0 6.0 6.0)))");
  std::string expectedWkt =
      "POLYHEDRALSURFACE Z (((5/1 6/1 6/1,5/1 6/1 5/1,5/1 5/1 6/1,5/1 6/1 "
      "6/1)),((5/1 5/1 6/1,5/1 6/1 5/1,5/1 5/1 5/1,5/1 5/1 6/1)),((6/1 5/1 "
      "5/1,6/1 5/1 6/1,5/1 5/1 6/1,6/1 5/1 5/1)),((5/1 5/1 5/1,6/1 5/1 5/1,5/1 "
      "5/1 6/1,5/1 5/1 5/1)),((5/1 5/1 5/1,5/1 6/1 5/1,6/1 5/1 5/1,5/1 5/1 "
      "5/1)),((6/1 5/1 5/1,5/1 6/1 5/1,6/1 6/1 5/1,6/1 5/1 5/1)),((6/1 5/1 "
      "6/1,6/1 6/1 6/1,5/1 6/1 6/1,6/1 5/1 6/1)),((5/1 5/1 6/1,6/1 5/1 6/1,5/1 "
      "6/1 6/1,5/1 5/1 6/1)),((5/1 6/1 5/1,5/1 6/1 6/1,6/1 6/1 5/1,5/1 6/1 "
      "5/1)),((6/1 6/1 5/1,5/1 6/1 6/1,6/1 6/1 6/1,6/1 6/1 5/1)),((6/1 5/1 "
      "6/1,6/1 5/1 5/1,6/1 6/1 5/1,6/1 5/1 6/1)),((6/1 6/1 6/1,6/1 5/1 6/1,6/1 "
      "6/1 5/1,6/1 6/1 6/1)))";
  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  // flaky
  // BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_EmptyGeometries)
{
  // Create empty geometries
  GeometryCollection emptyGeom1;
  GeometryCollection emptyGeom2;

  // Perform Minkowski sum
  std::unique_ptr<Geometry> result =
      algorithm::minkowskiSum3D(emptyGeom1, emptyGeom2);

  // Check that the result is an empty GeometryCollection
  BOOST_CHECK(result->isEmpty());
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_GEOMETRYCOLLECTION);

  std::string                     expectedWkt = "GEOMETRYCOLLECTION EMPTY";
  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  // BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_Square_Polyline_2D)
{
  // Create a square
  std::string               squareWkt = "POLYGON ((0 0, 0 1, 1 1, 1 0, 0 0))";
  std::unique_ptr<Geometry> square(io::readWkt(squareWkt));

  // Create a polyline
  std::string               polylineWkt = "LINESTRING (0 0, 1 1, 2 0)";
  std::unique_ptr<Geometry> polyline(io::readWkt(polylineWkt));

  // Perform Minkowski sum
  std::unique_ptr<Geometry> result =
      algorithm::minkowskiSum3D(*square, *polyline);

  // Check that the result is not empty
  BOOST_CHECK(!result->isEmpty());

  // Check that the result is a PolyhedralSurface (3D representation of the 2D
  // result)
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_POLYHEDRALSURFACE);

  std::string expectedWkt =
      "POLYHEDRALSURFACE Z (((3259801534828588929/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,4890278762995186817/1630477228166597888 "
      "-1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "1152921504606847/1152921504606846976,3259801534828588929/"
      "1630477228166597888 -1152921504606847/1630477228166597888 0/1)),((2/1 "
      "0/1 "
      "1152921504606847/1152921504606846976,3259801534828588929/"
      "1630477228166597888 -1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "1152921504606847/1152921504606846976,2/1 0/1 "
      "1152921504606847/1152921504606846976)),((3259801534828588929/"
      "1630477228166597888 -1152921504606847/1630477228166597888 0/1,2/1 0/1 "
      "-1152921504606847/1152921504606846976,3/1 0/1 "
      "-1152921504606847/1152921504606846976,3259801534828588929/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1)),((4890278762995186817/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,3259801534828588929/1630477228166597888 "
      "-1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "-1152921504606847/1152921504606846976,4890278762995186817/"
      "1630477228166597888 -1152921504606847/1630477228166597888 0/1)),((1/1 "
      "1/1 -1152921504606847/1152921504606846976,2/1 0/1 "
      "-1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1,1/1 1/1 "
      "-1152921504606847/1152921504606846976)),((1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1,2/1 0/1 "
      "-1152921504606847/1152921504606846976,3259801534828588929/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "0/1)),((1629324306661991041/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "0/1,3259801534828588929/1630477228166597888 "
      "-1152921504606847/1630477228166597888 0/1,2/1 0/1 "
      "1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1)),((1/1 "
      "1/1 "
      "1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1,2/1 0/1 "
      "1152921504606847/1152921504606846976,1/1 1/1 "
      "1152921504606847/1152921504606846976)),((1/1 1/1 "
      "1152921504606847/1152921504606846976,2/1 0/1 "
      "1152921504606847/1152921504606846976,3/1 0/1 "
      "1152921504606847/1152921504606846976,1/1 1/1 "
      "1152921504606847/1152921504606846976)),((2/1 2/1 "
      "1152921504606847/1152921504606846976,1/1 1/1 "
      "1152921504606847/1152921504606846976,3/1 1/1 "
      "1152921504606847/1152921504606846976,2/1 2/1 "
      "1152921504606847/1152921504606846976)),((3/1 1/1 "
      "1152921504606847/1152921504606846976,1/1 1/1 "
      "1152921504606847/1152921504606846976,3/1 0/1 "
      "1152921504606847/1152921504606846976,3/1 1/1 "
      "1152921504606847/1152921504606846976)),((1/1 2/1 "
      "1152921504606847/1152921504606846976,1/1 1/1 "
      "1152921504606847/1152921504606846976,2/1 2/1 "
      "1152921504606847/1152921504606846976,1/1 2/1 "
      "1152921504606847/1152921504606846976)),((3/1 0/1 "
      "1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "0/1,4892584606004400511/1630477228166597888 "
      "1631630149671204735/1630477228166597888 0/1,3/1 0/1 "
      "1152921504606847/1152921504606846976)),((3/1 1/1 "
      "1152921504606847/1152921504606846976,3/1 0/1 "
      "1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 0/1,3/1 1/1 "
      "1152921504606847/1152921504606846976)),((4890278762995186817/"
      "1630477228166597888 -1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "-1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "0/1,4890278762995186817/1630477228166597888 "
      "-1152921504606847/1630477228166597888 0/1)),((3/1 0/1 "
      "1152921504606847/1152921504606846976,4890278762995186817/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,4892584606004400511/1630477228166597888 "
      "1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "1152921504606847/1152921504606846976)),((3/1 0/1 "
      "-1152921504606847/1152921504606846976,3/1 1/1 "
      "-1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 0/1,3/1 0/1 "
      "-1152921504606847/1152921504606846976)),((4892584606004400511/"
      "1630477228166597888 1152921504606847/1630477228166597888 0/1,3/1 0/1 "
      "-1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "0/1,4892584606004400511/1630477228166597888 "
      "1152921504606847/1630477228166597888 0/1)),((1/1 2/1 "
      "-1152921504606847/1152921504606846976,2/1 2/1 "
      "-1152921504606847/1152921504606846976,1/1 1/1 "
      "-1152921504606847/1152921504606846976,1/1 2/1 "
      "-1152921504606847/1152921504606846976)),((1/1 1/1 "
      "-1152921504606847/1152921504606846976,2/1 2/1 "
      "-1152921504606847/1152921504606846976,3/1 1/1 "
      "-1152921504606847/1152921504606846976,1/1 1/1 "
      "-1152921504606847/1152921504606846976)),((1/1 1/1 "
      "-1152921504606847/1152921504606846976,3/1 1/1 "
      "-1152921504606847/1152921504606846976,3/1 0/1 "
      "-1152921504606847/1152921504606846976,1/1 1/1 "
      "-1152921504606847/1152921504606846976)),((1/1 1/1 "
      "-1152921504606847/1152921504606846976,3/1 0/1 "
      "-1152921504606847/1152921504606846976,2/1 0/1 "
      "-1152921504606847/1152921504606846976,1/1 1/1 "
      "-1152921504606847/1152921504606846976)),((1629324306661991041/"
      "1630477228166597888 3259801534828588929/1630477228166597888 0/1,1/1 2/1 "
      "-1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "3259801534828588929/1630477228166597888 "
      "0/1)),((1629324306661991041/1630477228166597888 "
      "1629324306661991041/1630477228166597888 0/1,1/1 2/1 "
      "-1152921504606847/1152921504606846976,1/1 1/1 "
      "-1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1)),((1/1 "
      "1/1 1152921504606847/1152921504606846976,1/1 2/1 "
      "1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1,1/1 1/1 "
      "1152921504606847/1152921504606846976)),((1629324306661991041/"
      "1630477228166597888 1629324306661991041/1630477228166597888 0/1,1/1 2/1 "
      "1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 3259801534828588929/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "1629324306661991041/1630477228166597888 0/1)),((1/1 2/1 "
      "1152921504606847/1152921504606846976,1631630149671204735/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "3259801534828588929/1630477228166597888 0/1,1/1 2/1 "
      "1152921504606847/1152921504606846976)),((1629324306661991041/"
      "1630477228166597888 3259801534828588929/1630477228166597888 "
      "0/1,1631630149671204735/1630477228166597888 "
      "3262107377837802623/1630477228166597888 0/1,1/1 2/1 "
      "-1152921504606847/1152921504606846976,1629324306661991041/"
      "1630477228166597888 3259801534828588929/1630477228166597888 0/1)),((2/1 "
      "2/1 "
      "1152921504606847/1152921504606846976,3262107377837802623/"
      "1630477228166597888 3262107377837802623/1630477228166597888 0/1,1/1 2/1 "
      "1152921504606847/1152921504606846976,2/1 2/1 "
      "1152921504606847/1152921504606846976)),((1/1 2/1 "
      "1152921504606847/1152921504606846976,3262107377837802623/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "0/1,1631630149671204735/1630477228166597888 "
      "3262107377837802623/1630477228166597888 0/1,1/1 2/1 "
      "1152921504606847/1152921504606846976)),((2/1 2/1 "
      "1152921504606847/1152921504606846976,3/1 1/1 "
      "1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 0/1,2/1 2/1 "
      "1152921504606847/1152921504606846976)),((3262107377837802623/"
      "1630477228166597888 3262107377837802623/1630477228166597888 0/1,2/1 2/1 "
      "1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "0/1,3262107377837802623/1630477228166597888 "
      "3262107377837802623/1630477228166597888 "
      "0/1)),((3262107377837802623/1630477228166597888 "
      "3262107377837802623/1630477228166597888 "
      "0/1,4892584606004400511/1630477228166597888 "
      "1631630149671204735/1630477228166597888 0/1,2/1 2/1 "
      "-1152921504606847/1152921504606846976,3262107377837802623/"
      "1630477228166597888 3262107377837802623/1630477228166597888 0/1)),((2/1 "
      "2/1 "
      "-1152921504606847/1152921504606846976,4892584606004400511/"
      "1630477228166597888 1631630149671204735/1630477228166597888 0/1,3/1 1/1 "
      "-1152921504606847/1152921504606846976,2/1 2/1 "
      "-1152921504606847/1152921504606846976)),((1631630149671204735/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "0/1,3262107377837802623/1630477228166597888 "
      "3262107377837802623/1630477228166597888 0/1,1/1 2/1 "
      "-1152921504606847/1152921504606846976,1631630149671204735/"
      "1630477228166597888 3262107377837802623/1630477228166597888 0/1)),((1/1 "
      "2/1 "
      "-1152921504606847/1152921504606846976,3262107377837802623/"
      "1630477228166597888 3262107377837802623/1630477228166597888 0/1,2/1 2/1 "
      "-1152921504606847/1152921504606846976,1/1 2/1 "
      "-1152921504606847/1152921504606846976)))";
  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  // flaky
  // BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_WKT_Cube_Point)
{
  std::string cubeWkt =
      "SOLID ((((0 0 0, 0 1 0, 1 1 0, 1 0 0, 0 0 0)), ((0 0 0, 0 0 1, 0 1 1, 0 "
      "1 0, 0 0 0)), ((0 0 0, 1 0 0, 1 0 1, 0 0 1, 0 0 0)), ((1 1 1, 0 1 1, 0 "
      "0 1, 1 0 1, 1 1 1)), ((1 1 1, 1 0 1, 1 0 0, 1 1 0, 1 1 1)), ((1 1 1, 1 "
      "1 0, 0 1 0, 0 1 1, 1 1 1))))";
  std::string pointWkt = "POINT (2 2 2)";

  std::unique_ptr<Geometry> cube(io::readWkt(cubeWkt));
  std::unique_ptr<Geometry> point(io::readWkt(pointWkt));

  std::unique_ptr<Geometry> result = algorithm::minkowskiSum3D(*cube, *point);

  BOOST_CHECK(!result->isEmpty());
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_POLYHEDRALSURFACE);

  std::string expectedWkt =
      "POLYHEDRALSURFACE Z (((2/1 3/1 3/1,2/1 3/1 2/1,2/1 2/1 3/1,2/1 3/1 "
      "3/1)),((2/1 2/1 3/1,2/1 3/1 2/1,2/1 2/1 2/1,2/1 2/1 3/1)),((3/1 2/1 "
      "2/1,3/1 2/1 3/1,2/1 2/1 3/1,3/1 2/1 2/1)),((2/1 2/1 2/1,3/1 2/1 2/1,2/1 "
      "2/1 3/1,2/1 2/1 2/1)),((2/1 2/1 2/1,2/1 3/1 2/1,3/1 2/1 2/1,2/1 2/1 "
      "2/1)),((3/1 2/1 2/1,2/1 3/1 2/1,3/1 3/1 2/1,3/1 2/1 2/1)),((3/1 2/1 "
      "3/1,3/1 3/1 3/1,2/1 3/1 3/1,3/1 2/1 3/1)),((2/1 2/1 3/1,3/1 2/1 3/1,2/1 "
      "3/1 3/1,2/1 2/1 3/1)),((2/1 3/1 2/1,2/1 3/1 3/1,3/1 3/1 2/1,2/1 3/1 "
      "2/1)),((3/1 3/1 2/1,2/1 3/1 3/1,3/1 3/1 3/1,3/1 3/1 2/1)),((3/1 2/1 "
      "3/1,3/1 2/1 2/1,3/1 3/1 2/1,3/1 2/1 3/1)),((3/1 3/1 3/1,3/1 2/1 3/1,3/1 "
      "3/1 2/1,3/1 3/1 3/1)))";
  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  // flaky
  // BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_CASE(testMinkowskiSum3D_WKT_Tetrahedron_Segment)
{
  std::string tetrahedronWkt =
      "SOLID ((((0 0 0, 1 0 0, 0 1 0, 0 0 0)), ((0 0 0, 0 1 0, 0 0 1, 0 0 0)), "
      "((0 0 0, 0 0 1, 1 0 0, 0 0 0)), ((1 0 0, 0 0 1, 0 1 0, 1 0 0))))";
  std::string segmentWkt = "LINESTRING (0 0 0, 1 1 1)";

  std::unique_ptr<Geometry> tetrahedron(io::readWkt(tetrahedronWkt));
  std::unique_ptr<Geometry> segment(io::readWkt(segmentWkt));

  BOOST_CHECK(tetrahedron != nullptr);
  BOOST_CHECK(segment != nullptr);

  BOOST_CHECK(!tetrahedron->isEmpty());
  BOOST_CHECK(!segment->isEmpty());

  BOOST_CHECK_EQUAL(tetrahedron->geometryTypeId(), TYPE_SOLID);
  BOOST_CHECK_EQUAL(segment->geometryTypeId(), TYPE_LINESTRING);

  std::unique_ptr<Geometry> result;
  BOOST_CHECK_NO_THROW(result =
                           algorithm::minkowskiSum3D(*tetrahedron, *segment));

  BOOST_CHECK(result != nullptr);
  BOOST_CHECK(!result->isEmpty());
  BOOST_CHECK_EQUAL(result->geometryTypeId(), TYPE_POLYHEDRALSURFACE);

  std::string expectedWkt =
      "POLYHEDRALSURFACE Z (((-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "1/1,-1152921504606847/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "0/1,-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "0/1,-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "1/1)),((-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "1/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016,-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016)),((-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "1/1,-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "0/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016)),((1152921504606847/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016,1152921504606847/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016)),((-1152921504606847/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "0/1,1152921504606847/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "0/1)),((1152921504606847/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "0/1,1152921504606847/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016)),((-1152921504606847/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "0/1,1152921504606847/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1152921504606847/1630477228166597888 "
      "0/1,-1152921504606847/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "0/1)),((2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,1629324306661991041/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "2/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016)),((-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,1629324306661991041/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "2/1,-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "1/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016)),((1629324306661991041/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "1/1,-1152921504606847/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "2/1,1629324306661991041/1630477228166597888 "
      "3262107377837802623/1630477228166597888 "
      "1/1)),((1629324306661991041/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "2/1,-1152921504606847/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "0/1,-1152921504606847/1630477228166597888 "
      "1152921504606847/1630477228166597888 "
      "1/1,1629324306661991041/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "2/1)),((2825222321273226879/2824069399768620032 "
      "5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016,1152921504606847/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1629324306661991041/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "1/1,2825222321273226879/2824069399768620032 "
      "5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016)),((1629324306661991041/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "1/1,1152921504606847/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016,-1152921504606847/"
      "1630477228166597888 1631630149671204735/1630477228166597888 "
      "0/1,1629324306661991041/1630477228166597888 "
      "3262107377837802623/1630477228166597888 "
      "1/1)),((1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "1/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1)),((-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1152921504606847/1412034699884310016)),((1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "1/1,1631630149671204735/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "2/1,2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "1/1)),((-1152921504606847/2824069399768620032 "
      "-1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "1/1,2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,-1152921504606847/"
      "2824069399768620032 -1152921504606847/2824069399768620032 "
      "1413187621388916863/1412034699884310016)),((1631630149671204735/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,2825222321273226879/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1631630149671204735/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1)),((2825222321273226879/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,1152921504606847/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,2825222321273226879/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016)),((1152921504606847/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016,2825222321273226879/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016)),((1631630149671204735/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "1/1,1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,1631630149671204735/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1)),((5649291721041846911/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016,2825222321273226879/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,2825222321273226879/"
      "2824069399768620032 5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016,5649291721041846911/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016)),((2825222321273226879/"
      "2824069399768620032 5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016,2825222321273226879/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,1152921504606847/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "-1152921504606847/1412034699884310016,2825222321273226879/"
      "2824069399768620032 5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016)),((1631630149671204735/"
      "1630477228166597888 1629324306661991041/1630477228166597888 "
      "2/1,3262107377837802623/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "1/1,2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,1631630149671204735/"
      "1630477228166597888 1629324306661991041/1630477228166597888 "
      "2/1)),((2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,3262107377837802623/"
      "1630477228166597888 1629324306661991041/1630477228166597888 "
      "1/1,5649291721041846911/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016,2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016)),((2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,5649291721041846911/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016,2825222321273226879/"
      "2824069399768620032 5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016,2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016)),((2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,2825222321273226879/"
      "2824069399768620032 5649291721041846911/2824069399768620032 "
      "1410881778379703169/1412034699884310016,1629324306661991041/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "1/1,2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016)),((2822916478264013185/"
      "2824069399768620032 2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016,1629324306661991041/"
      "1630477228166597888 3262107377837802623/1630477228166597888 "
      "1/1,1629324306661991041/1630477228166597888 "
      "1631630149671204735/1630477228166597888 "
      "2/1,2822916478264013185/2824069399768620032 "
      "2822916478264013185/2824069399768620032 "
      "2825222321273226879/1412034699884310016)),((1631630149671204735/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,3262107377837802623/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "1/1,1631630149671204735/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "2/1,1631630149671204735/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1)),((1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "1/1,1631630149671204735/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,1631630149671204735/1630477228166597888 "
      "1629324306661991041/1630477228166597888 "
      "2/1,1152921504606847/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "1/1)),((5649291721041846911/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016,3262107377837802623/"
      "1630477228166597888 1629324306661991041/1630477228166597888 "
      "1/1,1631630149671204735/1630477228166597888 "
      "-1152921504606847/1630477228166597888 "
      "0/1,5649291721041846911/2824069399768620032 "
      "2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016)),((2825222321273226879/"
      "2824069399768620032 1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016,5649291721041846911/"
      "2824069399768620032 2825222321273226879/2824069399768620032 "
      "1410881778379703169/1412034699884310016,1631630149671204735/"
      "1630477228166597888 -1152921504606847/1630477228166597888 "
      "0/1,2825222321273226879/2824069399768620032 "
      "1152921504606847/2824069399768620032 "
      "-1152921504606847/1412034699884310016)))";
  std::unique_ptr<Geometry> const expected(io::readWkt(expectedWkt));
  // flaky
  // BOOST_CHECK_EQUAL(result->asText(), expectedWkt);
  BOOST_CHECK(algorithm::covers3D(*result, *expected));
}

BOOST_AUTO_TEST_SUITE_END()
